package com.interview.javabasic.Sort;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {8,4,5,7,1,3,6,2};
        int temp[] =new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("排序后："+ Arrays.toString(arr));
    }

    //分+合
    public static void mergeSort(int arr[],int left,int right,int[] tmp){
        if (left<right){
            int mid = (left + right) /2;
            mergeSort(arr,left,mid,tmp);
            mergeSort(arr,mid+1,right,tmp);

            merge(arr,left,mid,right,tmp);
        }
    }

    //左边有序序列的初始索引中间索引，右边索引，
    public static void merge(int arr[],int left,int mid,int right,int[] tmp){
        int i = left;//左边有序序列的初始索引
        int j = mid + 1; //初始化j,右边有序序列的初始索引
        int t = 0;//指向tmp数组的当前索引

        //先把左右两边的有序数据按照规则填充到tmp数组中
        //直到左右两边有一边处理完毕
        while (i<=mid && j<=right){
            if (arr[i]<=arr[j]){
                tmp[t] = arr[i];
                t+=1;
                i+=1;
            }else{
                tmp[t] = arr[j];
                t+=1;
                j+=1;
            }
        }
        //将剩下的没有处理完毕的数组直接填充到tmp中
        while (i <= mid){//左边还有剩余，全部填充到tmp中
            tmp[t] = arr[i];
            t+=1;
            i+=1;
        }
        while (j <= right){
            tmp[t] = arr[j];
            t+=1;
            j+=1;
        }
        //将tmp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有的值
        t = 0;
        int tmpleft = left;
        while (tmpleft <= right){
            arr[tmpleft] = tmp[t];
            t+=1;
            tmpleft+=1;
        }
    }
}
